package sort;

public class ShellSort implements ISort{
	public void sort(int[] arr) {
		int gap = arr.length / 2;
		while(gap >= 1) {					//增量直到缩小到1为止
			for(int i = 0;i<gap;i++) {
				insertSort(arr, i, gap);    //每个分组内采用直接插入排序
			}
			gap = gap / 2;
		}
	}
	
	public void insertSort(int[] arr,int start,int gap) {
		int i = start + gap;
		while(i<arr.length) {
			int tmp = arr[i];
			int j = i - gap;
			while(j >= start) {
				if (tmp < arr[j]) {
					arr[j + gap] = arr[j];
					if(j==start) {
						arr[start] = tmp;
					}
				} else {
					arr[j + gap] = tmp;
					break;
				}
				j -= gap;
			}
			i += gap;
		}
	}
	
	public static void main(String[] args) {
		int arr[] = { 8, 4, 7, 9, 6, 3, 1, 2, 5 };
		ShellSort shellSort = new ShellSort();
		shellSort.sort(arr);
		ISort.printArr(arr);
	}

}
